dofile("utf8data.lua")
dofile("utf8.lua")
local string_len, string_sub = string.utf8len, string.utf8sub

local lcs
do
--[[
	lcs is an implementation in lua of the algorithm described in the paper :
		`An Algorithm for Differential File Comparison'
	by J. W. Hunt and M. D. McIlroy
	
	The paper can be downloaded from http://www.cs.dartmouth.edu/~doug/diff.ps
	
	The algorithm takes 2 strings and outputs a list of indexes. For each 
	character in the first string, either 0 (meaning that no correspondance has
	been found) or the index of the corresponding character in the second 
	string is returned.
]]
	local function candidate(a, b, previous)
		return { a = a, b = b, previous = previous }
	end

	local function merge(K, k, i, E, p)
		-- 1
		local r, c = 0, K[0]
		-- 2
		while true do
			-- 3
			local j = E[p].serial
			for s = r, k do
				if K[s].b < j and K[s + 1].b > j then
					-- 4
					if K[s + 1].b > j then
						K[r], r, c = c, s + 1, candidate(i, j, K[s])
					end
					-- 5
					if s == k then
						K[k + 2], k = K[k + 1], k + 1
					end
					break
				end
			end
			-- 6
			if E[p].last then
				break
			else
				p = p + 1
			end
		end
		-- 7
		K[r] = c
		
		return k
	end

	local function H(s, p)
		return string_sub(s, p, p)
	end

	local function sort_V(x, y)
		if x.hash ~= y.hash then
			return x.hash < y.hash
		else
			return x.serial < y.serial
		end
	end

	lcs = function (a, b)
		local m, n = string_len(a), string_len(b)
		-- 1 : V
		local V = {}
		for j = 1, n do
			V[j] = {serial = j, hash = H(b, j)}
		end
		-- 2 : sort
		table.sort(V, sort_V)
		-- 3 : E
		local E = {}
		E[0] = {serial = 0, last = true}
		for j = 1, n do
			E[j] = {
				serial = V[j].serial,
				last = (j == n or V[j].hash ~= V[j + 1].hash)
			}
		end
		-- 4 : P
		local P = {}
		for i = 1, m do
			local value
			for j = 1, n do
				if E[j - 1].last and H(a, i) == V[j].hash then
					value = j
					break
				end
			end
			P[i] = value or 0
		end
		-- 5 : K, k
		local K, k = {}, 0
		K[0] = { a = 0, b = 0 }
		K[1] = { a = m + 1, b = n + 1 }
		-- 6 : merge
		for i = 1, m do
			if P[i] ~= 0 then
				k = merge(K, k, i, E, P[i])
			end
		end
		-- 7 : J
		local J = {}
		for i = 0, m do
			J[i] = 0
		end
		-- 8
		local c = K[k]
		while c do
			J[c.a] = c.b
			c = c.previous
		end
		return J
	end
end

local function build_seq(J)
	local result = {}
	for i = 1, #J do
		local type = J[i] == 0 and "diff" or "same"
		if #result == 0 or result[#result].type ~= type then
			if #result > 0 then
				result[#result].len = i - result[#result].start
			end
			result[#result + 1] = { type = type, start = i }
		end
		result[#result].stop = i
	end
	if #result > 0 then
		result[#result].len = #J + 1 - result[#result].start
	end
	return result
end

local function mkdiffs(dst, src, ...)
	local J = lcs(dst, src)
	
	for i = 1, select("#", ...) do
		local c = select(i, ...)
		if c ~= dst and c ~= src then
			local Jc = lcs(dst, c)
			for j = 1, #J do
				if J[j] ~= 0 and Jc[j] == 0 then 
					J[j] = 0
				end
			end
		end
	end
	
	for i = 1, #J do
		if J[i] == 0 and tonumber(string_sub(dst, i, i)) then
			local p = i - 1
			while p >= 1 and tonumber(string_sub(dst, p, p)) do
				J[p] = 0
				p = p - 1
			end
			p = i + 1
			while p <= #J and tonumber(string_sub(dst, p, p)) do
				J[p] = 0
				p = p + 1
			end
		end
	end
	
	local fmt = {}
	local i = 1
	while i <= #J do
		local v, o = J[i] ~= 0, i + 1
		while o <= #J and (J[o] ~= 0) == v do
			o = o + 1
		end
		if v then
			fmt[#fmt + 1] = string_sub(dst, i, o - 1):gsub("%%", "%%%%")
		else
			fmt[#fmt + 1] = "%s"
		end
		i = o
	end
	fmt = table.concat(fmt)
	
	local pattern = "^" .. fmt
		:gsub("%-", "%%%-")
		:gsub("%.", "%%%.")
		:gsub("%*", "%%%*")
		:gsub("%[", "%%%[")
		:gsub("%]", "%%%]")
		:gsub("%(", "%%%(")
		:gsub("%)", "%%%)")
		:gsub("%%s", "(%.%*)")
		.. "$"
		
	local results = {}
	for i = 1, select("#", ...) do
		local c = select(i, ...)
		results[i] = {c:match(pattern)}
		if #results[i] == 0 then
			print("MISMATCH", pattern, c)
			return nil, "MISMATCH"
		elseif #results[i] > 4 then
			return nil, "TOO COMPLEX"
		end
	end
	
	return fmt, results
end

function build_diffs(...)
	if select("#", ...) < 2 then return nil, "SINGLE" end
	local i, j = 1
	for j = 2, select("#", ...) do
		if select(j, ...):len() > select(i, ...):len() then
			i = j
		end
	end
	if i == 1 then
		j = 2
	else
		j = 1
	end
	return mkdiffs(select(i, ...), select(j, ...), ...)
end

